import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);

        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println(list);
        System.out.println("====");
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        System.out.println("===========");
        for(int x : list) {
            System.out.print(x +" ");
        }
        System.out.println();
        System.out.println("======");

        ListIterator<Integer> it = list.listIterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }
        System.out.println();
        System.out.println("======");
        ListIterator<Integer> it2 = list.listIterator(list.size());
        while (it2.hasPrevious()) {
            System.out.print(it2.previous()+" ");
        }
        System.out.println();
    }

    public static void main4(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.clear();


        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(1);
        myLinkedList.addLast(2);
        myLinkedList.addLast(3);
        //myLinkedList.addIndex(2,14);
        myLinkedList.display();

        myLinkedList.clear();
        System.out.println("====");
        myLinkedList.display();

    }

    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode headA,
                                                      MySingleList.ListNode headB) {
        //实例化 静态内部类对象
        MySingleList.ListNode newHead = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmp = newHead;
        //保证两个链表都有数据
        while(headA != null && headB != null) {
            if(headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            }else {
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        if(headA != null) {
            tmp.next = headA;
        }
        if(headB != null) {
            tmp.next = headB;
        }
        return newHead.next;
    }

    public MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        int lenA = 0;
        int lenB = 0;

        MySingleList.ListNode pl = headA;//pl永远指向最长的链表
        MySingleList.ListNode ps = headB;//ps永远指向最长的链表

        //1.分别求长度
        while(pl != null) {
            lenA++;
            pl = pl.next;
        }
        while(ps != null) {
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        int len = lenA - lenB;
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB-lenA;
        }
        //保证pl指向最长的 ps指向最短的  len一定是正数
        //2、让pl先走len步
        while(len != 0) {
            pl = pl.next;
            len--;
        }
        //保证pl ps 将来走到相遇节点 的路程是一样的
        //3. 一人 一步走
        while(pl != null && ps != null &&  pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        if(pl == ps && pl == null) {
            return null;
        }
        return pl;
    }

    private void createCut(MySingleList.ListNode headA,
                           MySingleList.ListNode headB) {
        headB.next = headA.next.next;
    }

    public static void main3(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(11);
        mySingleList.addLast(21);
        mySingleList.addLast(41);
        mySingleList.addLast(51);

        mySingleList.display();

        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(13);
        mySingleList2.addLast(24);
        mySingleList2.addLast(34);
        mySingleList2.addLast(91);

        mySingleList2.display();

        MySingleList.ListNode  ret = mergeTwoLists(mySingleList.head,mySingleList2.head);

        mySingleList2.display(ret);

    }

    public static void main2(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(4);
        mySingleList.addLast(5);

        mySingleList.display();

        System.out.println("翻转....");
        MySingleList.ListNode ret = mySingleList.reverseList();

        mySingleList.display(ret);
    }
    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();
        //mySingleList.createList();
        mySingleList.addIndex(0,12);
        mySingleList.addLast(12);
        mySingleList.addLast(12);
        mySingleList.addLast(12);
        mySingleList.addLast(12);
        mySingleList.addIndex(3,12);
        System.out.println("===");
        mySingleList.display();//

        mySingleList.removeAllKey(12);
        System.out.println("=====================");
        mySingleList.display();//

       /* System.out.println(mySingleList.contains(12));
        System.out.println(mySingleList.size());*/
    }
}
